package cn.zifangsky.tree.binarytree.questions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 对于一棵给定的二叉树，输出所有从根节点到叶子节点的路径
 * @author zifangsky
 *
 */
public class Question13 {

	/**
	 * 通过前序遍历递归找出从根节点到叶子节点的所有路径
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void printPathsByPreOrder(BinaryTreeNode<Integer> root){
		if(root == null){
			System.out.println("Tree Empty");
			return;
		}
		
		printByPreOrderCore(root,new LinkedList<BinaryTreeNode<Integer>>());
	}
	
	/**
	 * 递归前序遍历并打印路径
	 * @param root
	 * @param list
	 */
	public void printByPreOrderCore(BinaryTreeNode<Integer> root,LinkedList<BinaryTreeNode<Integer>> list){
		list.add(root);
		
		//如果当前节点是叶子节点，则输出完整路径
		if(root.getLeft() == null && root.getRight() == null){
			for(BinaryTreeNode<Integer> tmpNode : list){
				System.out.print(tmpNode.getData() + " ");
			}
			System.out.println();
			list.removeLast(); //返回到上一层节点的时候从list中移除该叶子节点
			return;
		}
		
		if(root.getLeft() != null){
			printByPreOrderCore(root.getLeft(), list);
		}
		
		if(root.getRight() != null){
			printByPreOrderCore(root.getRight(), list);
		}
		list.removeLast(); //一个节点的左子树和右子树都遍历完了，则从list中删除该节点
	}
	
	
	/**
	 * 找出所有从根节点到叶子节点的路径
	 * 思路：
	 * 		层次遍历，每个路径用一个链表存储（倒序存储，每次在表头插入新节点），所有路径添加到List集合中
	 * @时间复杂度 O(n²)
	 * @param root
	 * @return
	 */
	public void printPaths(BinaryTreeNode<Integer> root){
		if(root == null){
			System.out.println("Tree Empty");
			return;
		}
		
		List<SinglyNode<BinaryTreeNode<Integer>>> result = new ArrayList<>(); //所有路径的List集合
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>(); //队列，用于辅助层次遍历

		result.add(new SinglyNode<BinaryTreeNode<Integer>>(root)); //添加这条路径
		queue.push(root); //根节点入队
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> tempBinaryTreeNode = queue.pop(); //出队
			
			/**
			 * 一个节点出队后，从存储所有路径的List集合中找出包含这个节点的路径（PS：有且只有一条从根节点到该节点的路径）。
			 * 如果这个节点存在左孩子节点，则将原路径链表从List中移除，再添加新的路径链表（PS：该链表在原来的基础之后在表头插入了这个左孩子节点）
			 * 如果这个节点存在右孩子节点，类似上面处理即可
			 */
			for(SinglyNode<BinaryTreeNode<Integer>> oldHeadNode : result){
				if(tempBinaryTreeNode == oldHeadNode.getData()){
					boolean isDel = false; //用于在该节点同时存在左孩子节点和右孩子节点的时候，在第一次从List中删除原路径之后第二次就不用再删除了
					
					//左子树生成一条新路径
					if(tempBinaryTreeNode.getLeft() != null){
						//移除原路径，后面添加新路径
						result.remove(oldHeadNode);
						isDel = true;
						
						//左孩子节点插入到该路径链表的表头位置
						SinglyNode<BinaryTreeNode<Integer>> newHeadNode = new SinglyNode<BinaryTreeNode<Integer>>(tempBinaryTreeNode.getLeft());
						newHeadNode.setNext(oldHeadNode);
						
						//在List中添加这个新路径，此左孩子节点入队
						result.add(newHeadNode);
						queue.push(tempBinaryTreeNode.getLeft());
					}
					
					//右子树生成一条新路径
					if(tempBinaryTreeNode.getRight() != null){
						if(!isDel){
							result.remove(oldHeadNode);
						}
						
						SinglyNode<BinaryTreeNode<Integer>> newHeadNode = new SinglyNode<BinaryTreeNode<Integer>>(tempBinaryTreeNode.getRight());
						newHeadNode.setNext(oldHeadNode);
						
						result.add(newHeadNode);
						queue.push(tempBinaryTreeNode.getRight());
					}
					
					break;
				}
				
				
			}
		
		}
	
		//倒序遍历最后得到的所有路径
		for(SinglyNode<BinaryTreeNode<Integer>> oldHeadNode : result){
			printLinkListFromEnd(oldHeadNode);
			System.out.println();
		}
	}
	
	
	
	
	/**
	 * 改进版找出所有从根节点到叶子节点的路径
	 * 思路：
	 * 		层次遍历，每个路径用一个链表存储（倒序存储，每次在表头插入新节点），所有路径添加到Map集合中
	 * @时间复杂度 O(n)
	 * @param root
	 * @return
	 */
	public void advancedPrintPaths(BinaryTreeNode<Integer> root){
		if(root == null){
			System.out.println("Tree Empty");
			return;
		}

		/**
		 * 所有路径存储在HashMap中
		 * key：每条路径在二叉树中最深的那个节点，也就是路径链表的表头节点的数据域
		 * value：路径链表的表头节点
		 */
		Map<BinaryTreeNode<Integer>, SinglyNode<BinaryTreeNode<Integer>>> result = new HashMap<>(); //
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>(); //队列，用于辅助层次遍历

		result.put(root, new SinglyNode<BinaryTreeNode<Integer>>(root));
		queue.push(root); //根节点入队
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> tempBinaryTreeNode = queue.pop(); //出队
			
			/**
			 * 一个节点出队后，从存储所有路径的Map集合中取出这个节点所在的路径（PS：有且只有一条从根节点到该节点的路径）。
			 * 如果这个节点存在左孩子节点，则将原路径链表从Map中移除，再添加新的路径链表（PS：该链表在原来的基础之后在表头插入了这个左孩子节点）
			 * 如果这个节点存在右孩子节点，类似上面处理即可
			 */
			SinglyNode<BinaryTreeNode<Integer>> oldHeadNode = result.get(tempBinaryTreeNode);
			boolean isDel = false; //用于在该节点同时存在左孩子节点和右孩子节点的时候，在第一次从Map中删除原路径之后第二次就不用再删除了
			
			//左子树生成一条新路径
			if(tempBinaryTreeNode.getLeft() != null){
				//移除原路径，后面添加新路径
				result.remove(tempBinaryTreeNode);
				isDel = true;
				
				//左孩子节点插入到该路径链表的表头位置
				SinglyNode<BinaryTreeNode<Integer>> newHeadNode = new SinglyNode<BinaryTreeNode<Integer>>(tempBinaryTreeNode.getLeft());
				newHeadNode.setNext(oldHeadNode);
				
				//在Map中添加这个新路径，此左孩子节点入队
				result.put(tempBinaryTreeNode.getLeft(), newHeadNode);
				queue.push(tempBinaryTreeNode.getLeft());
			}
			
			//右子树生成一条新路径
			if(tempBinaryTreeNode.getRight() != null){
				if(!isDel){
					result.remove(tempBinaryTreeNode);
				}
				
				SinglyNode<BinaryTreeNode<Integer>> newHeadNode = new SinglyNode<BinaryTreeNode<Integer>>(tempBinaryTreeNode.getRight());
				newHeadNode.setNext(oldHeadNode);
				
				result.put(tempBinaryTreeNode.getRight(), newHeadNode);
				queue.push(tempBinaryTreeNode.getRight());
			}
		}
	
		//倒序遍历最后得到的所有路径
		for(SinglyNode<BinaryTreeNode<Integer>> oldHeadNode : result.values()){
			printLinkListFromEnd(oldHeadNode);
			System.out.println();
		}
	}
	
	/**
	 * 从表尾开始遍历链表
	 * @param headNode
	 */
	private void printLinkListFromEnd(SinglyNode<BinaryTreeNode<Integer>> headNode){
		if(headNode != null){
			if(headNode.getNext() != null){
				printLinkListFromEnd(headNode.getNext());
			}
			
			System.out.print(headNode.getData().getData() + " ");
		}
	}
	


	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<1000000;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.push(tmpNode1);
			queue.push(tmpNode2);
		}

		long date1 = System.currentTimeMillis();
//		printPaths(root);
//		advancedPrintPaths(root);
		printPathsByPreOrder(root);
		System.out.println("花费时间： " + (System.currentTimeMillis() - date1));
	}

	@Test
	public void testLinkedList(){
		LinkedList<Integer> list = new LinkedList<>();
		
		for(int i=0;i<10;i++){
			list.add(i);
		}
		
//		System.out.println(list.peek());
//		System.out.println(list.peek());
		System.out.println("." + list.poll());
		list.add(list.poll());
		System.out.println("." + list.poll());
		
		for(Integer i : list){
			System.out.println(i);
		}
	}
	
}
